public class ProductExceptSelf {
    // 除自身以外数组的乘积
    // https://leetcode.cn/problems/product-of-array-except-self/?envType=study-plan-v2&envId=top-100-liked
    public int[] productExceptSelf(int[] nums) {
        long[] leftProduct = new long[nums.length];
        long[] rightProduct = new long[nums.length];
        long product= 1;
        for (int i = 0; i < nums.length; i++) {
            leftProduct[i] = product;
            product *= nums[i];
        }
        product = 1;
        for (int i = nums.length-1; i >= 0; i--) {
            rightProduct[i] = product;
            product *= nums[i];
        }
        int[] ret = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            ret[i] = (int)(leftProduct[i] * rightProduct[i]);
        }
        return ret;
    }
}
